#include "SortAlgorithms.h"
#include<iostream>
using namespace std;
void HeapSort::Sort(int *inputArray, int size)
{
	//build the max heap
	BuildMaxHeap (inputArray, size);

	//we go through the heap starting from the last element in the array
	//and we go down to the root. we take the root out by putting it in place of
	//the last element and we decrement the size of the array
	//essentialy making the last element, which was our root to beging with
	//unreachable. then we do a maxheapify on the remaining elements in 
	//the array to maintain the heap property and repeat the process with 
	//the remaining elements in the array
	for(int i = size - 1; i > 0; i--)
	{
		int temp = inputArray[0];
		inputArray[0] = inputArray[i];
		inputArray[i] = temp;
		size--;
		MaxHeapify (inputArray, 0, size);
	}
	return;
}
void HeapSort::BuildMaxHeap(int *inputArray, int size)
{
	//The Build-Max-Heap function that follows, converts an array A  
	//which stores a complete binary tree with n nodes to a max-heap by 
	//repeatedly using Max-Heapify in a bottom up manner. 
	//It is based on the observation that the array elements indexed by 
	//floor(n/2) + 1, floor(n/2) + 2, ... , n are all leaves for the tree, 
	//thus each is an one-element heap
	for(int i = size/2; i>= 0; i--)
	{
		MaxHeapify(inputArray, i, size);
	}
}

void HeapSort::MaxHeapify(int *inputArray, int index, int size)
{
	//let the index of the largest element be the one that was 
	//passed in for now
	int largestIndex = index;
	int leftIndex = left(index);
	int rightIndex = right(index);

	//ensure that the leftIndex will not go out of bounds
	if(leftIndex < size)
	{
		//if the value at the left child is greater than 
		//the current largest index, then make the 
		//largest index be the left child's index
		if(inputArray[leftIndex] > inputArray[largestIndex])
		{
			largestIndex = leftIndex;
		}
	}

	//ensure that the rightIndex will not go out of bounds
	if(rightIndex < size)
	{
		//if the value at the right child is greater than 
		//the current largest index, then make the 
		//largest index be the right child's index
		if(inputArray[rightIndex] > inputArray[largestIndex])
		{
			largestIndex = rightIndex;
		}
	}
	//if the index of the largest element was changed
	//swap the value of the child with the value of the root
	//to maintain the max heap property
	if(largestIndex != index)
	{
		int temp = inputArray[index];
		inputArray[index] = inputArray[largestIndex];
		inputArray[largestIndex] = temp;

		//since the child was swapped with it's parent
		//now we have to max heapify the child to maintain the max
		//heap property. since the child was the largest index, we pass
		//the largest index to the MaxHeapify method
		MaxHeapify (inputArray, largestIndex, size);
		
	}
	return;
}

int HeapSort::parent(int i)
{
	//for odd indexed children the parent is at i/2
	int parent = i/2;
	//for even indexed children the parent is at i/2 -1
	if(i % 2 == 0)
	{
		parent = parent - 1;
	}
	
	return parent;
}

int HeapSort::left(int i)
{
	//left child is at 2*i(index of self) + 1
	return 2*i + 1;
}

int HeapSort::right(int i)
{
		//right child is at 2*i(index of self) + 2
	return	2* i + 2;
}